home *** CD-ROM | disk | FTP | other *** search
- Path: keats.ugrad.cs.ubc.ca!not-for-mail
- From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
- Newsgroups: comp.lang.c
- Subject: Re: REQUEST: Recursive functions
- Date: 25 Mar 1996 13:18:41 -0800
- Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
- Message-ID: <4j72jhINNp77@keats.ugrad.cs.ubc.ca>
- References: <4h7lft$8ql@cis.clark.edu> <3150334B.1802@willows.com> <827630695snz@genesis.demon.co.uk> <1996Mar25.125041.116595@kuhub.cc.ukans.edu>
- NNTP-Posting-Host: keats.ugrad.cs.ubc.ca
-
- In article <1996Mar25.125041.116595@kuhub.cc.ukans.edu>,
- <anh@kuhub.cc.ukans.edu> wrote:
- >A classic way to find one's way through a 2D maze is to always keep to the
- >right. In other words, if you arrive at an intersection, turn right,
- >eventually you will find your way out. Now if your maze's only exit is
- >the entrance you will come back to the entrance after you have visited
- >the whole maze, and, hence, you must have encountered the cheese on the
- >way. If there are multiple exits, well, just make sure you mark the
- >entrance to know when to quit searching.
-
- False. You will visit the whole maze if it is isomorphic to a connected,
- acyclic graph. Then, the search you describe is basically a depth-first
- traversal.
-
- If the maze has cycles, you will end up not visiting some of the cells. You
- might not even find your way out, if the starting point is in the centre, and
- the rule of keeping to the right forces you to follow a wall that is surrounded
- by a loop.
- --
-
-